package java学习.代码随想录.动态规划;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/9/14 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 密室逃脱 {

    /**
     1.玩家初始位置在1号密室；
     2.每次玩家可以进入右边的一个密室，也可以跳过一个密室进入下个密室（如：当玩家当前在3号密室，他可以进入4号密室也可以进入5号密室）；
     3.有毒气的密室不能进入需要避开。

     现给定三个正整数X，Y，M（1<X<Y<M≤40），表示三个密室编号。X号密室和Y号密室有毒气泄漏，不能进入，玩家需要进入到M号密室。按照游戏规则进入M号密室有多少种路线方案。
     2 4 7 输出 2

     例如：X=2，Y=4，M=7，2号和4号有毒气泄露，避开2号和4号毒气密室，进入7号密室有2种路线方案，分别是1->3->5->6->7路线和1->3->5->7路线。
      dp[i]:绕过X、Y的路线 到达 i的个数。
         0 1 2 3 4 5 6 7
           1 2 3 4 5 6 7
 dp[i]   0 1 0 1 0 1 1 2
 dp[i] = dp[i-1]+ dp[i-2]
     */
    public static void main(String[] args) {
        int x = 2,y=4,m=7;
//        int x = 2,y=8,m=24;
        System.out.println(MiShiTaoTuo(x,y,m));
    }
    public static int MiShiTaoTuo(int x,int y,int m){

        int [] dp = new int[m+1];
        if (x!=1&&y!=1){
            dp[1] = 1;
        }
        if (x!=2&&y!=2){
            dp[2] = 1;
        }
        for (int i = 2; i < m+1; i++) {
            if (i==x||i==y){
                dp[i] = 0;
            }else{
                dp[i] = dp[i-1]+dp[i-2];
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[m];
    }
}
